package com.example.leetcode.tree;

import com.example.leetcode.tree.common.TreeNode;
import com.example.leetcode.tree.common.TreeUtils;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
 *
 * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 *
 * 提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,2,3,null,null,4,5]
 * 输出：[1,2,3,null,null,4,5]
 * 示例 2：
 *
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [1]
 * 输出：[1]
 * 示例 4：
 *
 * 输入：root = [1,2]
 * 输出：[1,2]
 *
 *
 * 提示：
 *
 * 树中结点数在范围 [0, 104] 内
 * -1000 <= Node.val <= 1000
 */
public class leetcode297 {
    public static void main(String[] args) {
        Integer[] nums = {1, 2, 3, null, null, 4, 5};
        TreeNode root = TreeUtils.generateLeetcodeTree(nums);

        Codec ser = new Codec();
        Codec deser = new Codec();
        TreeNode ans = deser.deserialize(ser.serialize(root));

        System.out.println(ans);
    }

//    /**
//     * 使用前序遍历
//     */
//    static class Codec {
//        // Encodes a tree to a single string.
//        public String serialize(TreeNode root) {
//            if (root == null) return "null";
//            return root.val + "," + serialize(root.left) + "," + serialize(root.right);
//        }
//
//        // Decodes your encoded data to tree.
//        public TreeNode deserialize(String data) {
//            LinkedList<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
//            return buildTree(nodes);
//        }
//
//        private TreeNode buildTree(LinkedList<String> nodes) {
//            String val = nodes.poll();
//            if (val.equals("null")) return null;
//
//            TreeNode node = new TreeNode(Integer.parseInt(val));
//            node.left = buildTree(nodes);
//            node.right = buildTree(nodes);
//            return node;
//        }
//    }

    static class Codec {
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) return "null";

            StringBuilder sb = new StringBuilder();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode curr = queue.poll();
                if (curr != null) {
                    sb.append(curr.val).append(",");
                    queue.offer(curr.left);
                    queue.offer(curr.right);
                } else {
                    sb.append("null,");
                }
            }
            return sb.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.equals("null")) return null;

            String[] nodes = data.split(",");
            TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int i = 1;
            while (!queue.isEmpty()) {
                TreeNode curr = queue.poll();
                if (!nodes[i].equals("null")) {
                    curr.left = new TreeNode(Integer.parseInt(nodes[i]));
                    queue.offer(curr.left);
                }
                i++;
                if (!nodes[i].equals("null")) {
                    curr.right = new TreeNode(Integer.parseInt(nodes[i]));
                    queue.offer(curr.right);
                }
                i++;
            }
            return root;
        }
    }


}
